package org.example.graph_theory;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class All_possible_paths {
    public static ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
    public static void main(String[] args) {
        //所有可能的路径

        //给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
        // graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
        //int[][] graph = {{1,2},{3},{3},{}};

        int[][] graph = {{4,3,1},{3,2,4},{3},{4},{}};
        List<List<Integer>> lists = allPathsSourceTarget(graph);
        System.out.println(lists);
    }
    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0);
        dfs(graph,0, list);
        return res;
    }
    public static void dfs(int[][] graph,int deep,LinkedList<Integer> list){
        if (!list.isEmpty() && list.getLast() == graph.length-1){
            res.add(new LinkedList<>(list));
            return;
        }
        for (int i = 0; i < graph[deep].length; i++) {
            list.add(graph[deep][i]);
            dfs(graph,graph[deep][i],list);
            list.removeLast();
        }
    }
}
